package cn.hashq;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class ShuduDemo {

    private static int n = 15;
    private static int[][] cols = {
            {6, 2, 1}, {2, 3, 2}, {2, 3}, {1, 5, 4, 2}, {2, 3},
            {6}, {5, 2, 2}, {1, 1, 2, 1}, {3, 1}, {2, 2, 6},
            {1, 7, 2, 1}, {2, 1}, {2, 3, 1, 1}, {1, 5, 7}, {2}
    };
    private static int[][] rows = {
            {1, 2, 2, 1}, {1, 1, 1, 1, 2}, {2, 2, 1, 2, 2}, {1, 1, 2, 2, 1}, {1, 2, 1, 1, 1},
            {1, 2, 1, 1, 1}, {1, 2, 1, 5}, {1, 1, 1, 2, 1}, {1, 2, 1, 1, 2}, {1, 1, 2, 2, 1},
            {2, 1, 1, 2, 1}, {1, 2, 1, 2, 2}, {1, 1, 2, 1}, {3, 2, 1, 3}, {2, 1, 3, 2, 2}
    };

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        n = cols.length;
        int[][] matrix = new int[n][n];
        initMatrix(matrix);
        List<List<int[]>> allPossibleRows = new ArrayList<>();
        for (int[] row : rows) {
            List<int[]> possibleRows = generateAllPossibleRow(row, n);
            allPossibleRows.add(possibleRows);
        }
        initColRulesMatrix(matrix, cols);
        // 筛选不过关的可能性
        filterErrorRow(matrix, allPossibleRows);
        initMatrix(matrix);
        generateResult(allPossibleRows, matrix);
        System.out.println("耗时：" + (System.currentTimeMillis() - start));
    }

    private static int[] generateResult(List<List<int[]>> allPossibleRows, int[][] matrix) {
        int[] index = new int[n];
        boolean flag = true;
        while (flag) {
            for (int i = 0; i < allPossibleRows.size(); i++) {
                boolean next = false;
                while (!next) {
                    List<int[]> currentRow = allPossibleRows.get(i);
                    if (index[i] >= currentRow.size()) {
                        // 回溯
                        index[i] = 0;
                        Arrays.fill(matrix[i], 0, matrix[i].length, 2);
                        index[i - 1] = index[i - 1] + 1;
                        i = i - 2;
                        break;
                    }
                    int[] row = currentRow.get(index[i]);
                    matrix[i] = Arrays.copyOf(row, row.length);
                    if (i != 0) {
                        // 校验,不通过则index[i] ++
                        if (!verifyCol(matrix)) {
                            index[i] = index[i] + 1;
                            if (index[i] == currentRow.size()) {
                                index[i] = 0;
                                Arrays.fill(matrix[i], 0, row.length, 2);
                                // 回溯
                                index[i - 1] = index[i - 1] + 1;
                                i = i - 2;
                                break;
                            }
                        } else {
                            next = true;
                        }
                    } else {
                        next = true;
                    }
                }
            }
            if (isAllFill(matrix) && verifyCol(matrix)) {
                flag = false;
                printMatrix(matrix);
            }
        }
        return index;
    }

    private static void filterErrorRow(int[][] matrix, List<List<int[]>> allPossibleRows) {
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            List<int[]> currentRowPossibles = allPossibleRows.get(i);
            currentRowPossibles = currentRowPossibles.stream().filter(item -> {
                for (int j = 0; j < item.length; j++) {
                    if (row[j] != 2 && row[j] != item[j]) {
                        return false;
                    }
                }
                return true;
            }).collect(Collectors.toList());
            allPossibleRows.set(i, currentRowPossibles);
        }
    }

    private static boolean isAllFill(int[][] matrix) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 2) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean verifyCol(int[][] matrix) {
        for (int i = 0; i < n; i++) {
            int ruleIndex = 0;
            int count = -1;
            int[] colRule = cols[i];
            for (int j = 0; j < n; j++) {
                if (ruleIndex > colRule.length - 1) {
                    if (matrix[j][i] == 1) {
                        return false;
                    }
                    continue;
                }
                int ruleCount = colRule[ruleIndex];
                if (matrix[j][i] == 1) {
                    if (count == -1) {
                        count = 0;
                    }
                    count++;
                } else if (matrix[j][i] == 2) {
                    if (count != -1) {
                        if (ruleCount < count) {
                            return false;
                        } else {
                            // ruleCount >= count;
                            // 进行下一列
                            break;
                        }
                    }
                } else if (matrix[j][i] == 0) {
                    if (count != -1) {
                        if (ruleCount != count) {
                            return false;
                        }
                        count = -1;
                        ruleIndex++;
                    }
                } else {
                    if (count != -1) {
                        if (ruleCount != count) {
                            return false;
                        }
                        count = -1;
                        ruleIndex++;
                    }
                }
                if (j == n - 1) {
                    if (count != -1 && count != ruleCount) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 根据规则生成所有可能性
     *
     * @param rules 规则
     * @param n     容器长度
     * @return 所有可能性
     */
    private static List<int[]> generateAllPossibleRow(int[] rules, int n) {
        List<int[]> result = new ArrayList<>();
        int total = Arrays.stream(rules).sum();
        int pre = 0;
        int endLine = 0;
        for (int i = 0; i < rules.length; i++) {
            int count = rules[i];
            int start = pre;
            int end = n - (total - count) - (rules.length - 1) - count + pre;
            pre += count + 1;
            List<int[]> tmp = new ArrayList<>();
            for (int j = start; j <= end; j++) {
                if (i == 0) {
                    int[] row = new int[n];
                    Arrays.fill(row, 0);
                    Arrays.fill(row, j, j + count, 1);
                    result.add(row);
                } else {
                    // 上一次数量为截止
                    for (int k = 0; k < endLine; k++) {
                        int[] alreadyRow = result.get(k);
                        int[] newRow = Arrays.copyOf(alreadyRow, alreadyRow.length);
                        if (alreadyRow[j - 1] == 1) {
                            break;
                        }
                        Arrays.fill(newRow, j, j + count, 1);
                        tmp.add(newRow);
                    }
                }
            }
            if (!tmp.isEmpty()) {
                result.clear();
                result.addAll(tmp);
            }
            endLine = result.size();
        }

        return result;
    }


    /**
     * 初始化矩阵为未填写状态
     */
    private static void initMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            Arrays.fill(row, 2);
        }
    }


    private static void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            int[] row = matrix[i];
            printRow(row);
        }
    }

    private static void printRow(int[] row) {
        System.out.print("[");
        for (int j = 0; j < row.length; j++) {
            System.out.print(row[j]);
            if (j != row.length - 1) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }

    private static void initColRulesMatrix(int[][] matrix, int[][] cols) {
        int index = 0;
        for (int[] colRule : cols) {
            int total = Arrays.stream(colRule).sum();
            int alreadySum = 0;
            int[] tmpRow = new int[n];
            Arrays.fill(tmpRow, 2);
            boolean fill = false;
            for (int i = 0; i < colRule.length; i++) {
                int rule = colRule[i];
                // 前面必须要用的格子数量,同时也是起始填充位置
                int startPoint = alreadySum + i;
                // 后面必须要用到的格子
                int nextNeedCount = (total - rule - alreadySum) + (colRule.length - i - 1);
                int canUseCount = n - nextNeedCount - startPoint;

                if (canUseCount - rule < rule) {
                    Arrays.fill(tmpRow, startPoint + (canUseCount - rule), startPoint + (canUseCount - rule) + (canUseCount - (canUseCount - rule) * 2), 1);
                    fill = true;
                }
                alreadySum += rule;
            }
            if (fill) {
                for (int i = 0; i < tmpRow.length; i++) {
                    int[] row = matrix[i];
                    if (row[index] == 2) {
                        row[index] = tmpRow[i];
                    }
                }
            }
            index++;
        }
    }

    private static void initRowRulesMatrix(int[][] matrix) {
        int index = 0;
        for (int[] rowRules : rows) {
            int total = Arrays.stream(rowRules).sum();
            int alreadySum = 0;
            for (int i = 0; i < rowRules.length; i++) {
                int rule = rowRules[i];
                // 前面必须要用的格子数量,同时也是起始填充位置
                int startPoint = alreadySum + i;
                // 后面必须要用到的格子
                int nextNeedCount = (total - rule - alreadySum) + (rowRules.length - i - 1);
                int canUseCount = n - nextNeedCount - startPoint;

                if (canUseCount - rule < rule) {
                    int[] matrixRow = matrix[index];
                    Arrays.fill(matrixRow, startPoint + (canUseCount - rule), startPoint + (canUseCount - rule) + (canUseCount - (canUseCount - rule) * 2), 1);
                }
                alreadySum += rule;
            }
            index++;
        }
    }
}
